package mac5789.graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import mac5789.utils.Range;

/**
 * Grafo aleatório com número definido de vértices e grau de cada vértice. O
 * algoritmo utilizado foi descrito em Steger-Wormald 97.
 * 
 * @author lundberg
 * 
 */
public class StegerWormaldRandomGraph extends AbstractGraph {

    private final Random random;

    private final int degree;

    /**
     * Construtor
     * 
     * @param nVertexes
     *            nVertexes
     * @param degree
     *            degree
     * @param seed
     *            seed
     */
    public StegerWormaldRandomGraph(int nVertexes, int degree, long seed) {
        super(nVertexes);
        this.degree = degree;
        this.random = new Random(seed);
        this.initialize();
    }

    private void initialize() {
        while (!this.createEdges()) {
            this.clear();
        }
    }

    private boolean createEdges() {
        List<Point> points = new ArrayList<Point>();
        for (Integer vertex : new Range(0, this.getNVertexes())) {
            for (Integer index : new Range(0, this.degree)) {
                points.add(new Point(vertex, index));
            }
        }
        while (!points.isEmpty() && this.canAddEdges(points)) {
            Point aPoint = points.get(this.random.nextInt(points.size()));
            Point otherPoint = points.get(this.random.nextInt(points.size()));
            if (this.areSuitable(aPoint, otherPoint)) {
                this.addEdge(aPoint.getVertex(), otherPoint.getVertex());
                points.remove(aPoint);
                points.remove(otherPoint);
            }
        }
        return points.isEmpty();
    }

    private boolean areSuitable(Point aPoint, Point otherPoint) {
        return aPoint.getVertex() != otherPoint.getVertex() && !this.areNeighbours(aPoint.getVertex(), otherPoint.getVertex());
    }

    private boolean canAddEdges(List<Point> points) {
        if (points.size() < 2) {
            return false;
        }
        for (int i = 0; i < points.size() - 1; i++) {
            for (int j = i + 1; j < points.size(); j++) {
                if (points.get(i).getVertex() != points.get(j).getVertex() && !this.areNeighbours(points.get(i).getVertex(), points.get(j).getVertex())) {
                    return true;
                }
            }
        }
        return false;
    }

    public static class Point {
        private final Integer vertex;

        private final Integer index;

        public Point(Integer vertex, Integer index) {
            super();
            this.vertex = vertex;
            this.index = index;
        }

        /**
         * @return the vertex
         */
        public Integer getVertex() {
            return this.vertex;
        }

        @Override
        public String toString() {
            return "Point[" + this.vertex + "][" + this.index + "]";
        }
    }
}
